/*
 * @lc app=leetcode.cn id=590 lang=golang
 *
 * [590] N 叉树的后序遍历
 */

// 2-2. 循环
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func postorder(root *Node) (ans []int) {
	if root == nil {
		return
	}
	stack := []*Node{root}
	for len(stack) > 0 { // 根、右、左
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ans = append(ans, node.Val)
		stack = append(stack, node.Children...)
	}

	// 反转
	for i, n := 0, len(ans)-1; i <= n/2; i++ {
		ans[i], ans[n-i] = ans[n-i], ans[i]
	}
	return
}

// @lc code=end

// 2-1. 循环
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func postorder(root *Node) (ans []int) {
	if root == nil {
		return
	}
	stack := []*Node{root}
	m := make(map[*Node]int)
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		if len(node.Children) == 0 {
			ans = append(ans, node.Val)
			stack = stack[:len(stack)-1]
		} else {
			if v, ok := m[node]; ok && v == 1 {
				ans = append(ans, node.Val)
				stack = stack[:len(stack)-1]
			} else {
				m[node] = 1
				for i := len(node.Children) - 1; i >= 0; i-- {
					stack = append(stack, node.Children[i])
				}
			}
		}

	}
	return
}

// @lc code=end

// 1-2. 递归
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func postorder(root *Node) (ans []int) {
	var post func(nodes []*Node)
	post = func(nodes []*Node) {
		for i := 0; i < len(nodes); i++ {
			if nodes[i] != nil {
				post(nodes[i].Children)
				ans = append(ans, nodes[i].Val)
			}
		}
	}
	post([]*Node{root})
	return
}

// @lc code=end

// 1-1. 递归
// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func postorder(root *Node) (ans []int) {
	var post func(node *Node)
	post = func(node *Node) {
		if node == nil {
			return
		}
		for i := 0; node.Children != nil && i < len(node.Children); i++ {
			post(node.Children[i])
		}
		ans = append(ans, node.Val)
	}

	post(root)
	return
}

// @lc code=end

